#include<iostream>
#include<vector>
#include<unordered_map>
#include<utility>
using namespace std;

//912.排序数组

void mergesort(int left,int right,vector<int>& nums){
    //区间不存在，直接结束返回
    if(left>=right){
        return;
    }

    //1.分区间
    int mid = (right + left) / 2;
    //[left,mid],[mid+1,right]

    //2.递归子区间
    mergesort(left, mid, nums);
    mergesort(mid + 1, right, nums);

    //3.排序
    int cur1 = left, cur2 = mid + 1;
    int i = 0;
    //辅助数组
    vector<int> tmp(right - left + 1);
    while(cur1<=mid&&cur2<=right){
        tmp[i++] = (nums[cur1] <= nums[cur2]) ? nums[cur1++] : nums[cur2++];
    }
    while(cur1<=mid){
        tmp[i++] = nums[cur1++];
    }
    while(cur2<=right){
        tmp[i++] = nums[cur2++];
    }

    //4.还原
    for (int i = left;i<=right;i++){
        nums[i] = tmp[i - left];
    }
}
vector<int> sortArray(vector<int>& nums){
    mergesort(0, nums.size() - 1, nums);

    return nums;
}


//LCR.171.交易中的逆序对数
//通过归并排序查找逆序对数
int mergesort1(int left,int right,vector<int>& nums){
    //区间不存在，直接结束返回0
    if(left>=right){
        return 0;
    }

    //1.分区间 [left,mid]  [mid+1,right]
    int mid = (left + right) / 2;

    //2.递归左右子区间
    int Lret = mergesort1(left, mid, nums);
    int Rret = mergesort1(mid + 1, right, nums);

    //3.排序+左右查找逆序对个数
    int cur1 = left, cur2 = mid + 1;
    int i = 0;
    int ret = 0;
    vector<int> tmp(right - left + 1);
    //升序，找出该数之前有多少个比自己大的
    while(cur1<=mid&&cur2<=right){
        if(nums[cur1]>nums[cur2]){
            ret += mid - cur1 + 1;
            tmp[i++] = nums[cur2++];
        }
        else{
            tmp[i++] = nums[cur1++];
        }
    }
    /*//降序，找出该数之后有多少个比自己小的
    while(cur1<=mid&&cur2<=right){
        if(nums[cur1]>nums[cur2]){
            ret += right - cur2 + 1;
            tmp[i++] = nums[cur1++];
        }
        else{
            tmp[i++] = nums[cur2++];
        }
    }*/
    while(cur1<=mid){
        tmp[i++] = nums[cur1++];
    }
    while(cur2<=right){
        tmp[i++] = nums[cur2++];
    }

    //4.还原
    for (int i = left; i <= right;i++){
        nums[i] = tmp[i - left];
    }

    return ret + Lret + Rret;
}

int reversePairs(vector<int>& record){
    return mergesort1(0, record.size() - 1, record);
}

//计算右侧小于当前元素的个数
//归并统计每个数
void mergesort2(int left,int right,vector<pair<int,int>>& nums,vector<int>& counts){
    //区间不存在，直接结束返回
    if(left>=right){
        return;
    }

    //1.分区间
    int mid = (left + right) / 2;

    //2.递归左右子区间
    mergesort2(left, mid, nums, counts);
    mergesort2(mid + 1, right, nums, counts);

    //3.排降序，统计个数
    int cur1 = left, cur2 = mid + 1;
    int i = 0;
    vector<pair<int,int>> tmp(right - left + 1);

    while(cur1<=mid&&cur2<=right){
        if(nums[cur1].first>nums[cur2].first){
            counts[nums[cur1].second] += right - cur2 + 1;
            tmp[i].first = nums[cur1].first;
            tmp[i++].second = nums[cur1++].second;
        }
        else{
            tmp[i].first = nums[cur2].first;
            tmp[i++].second = nums[cur2++].second;
        }
    }
    while(cur1<=mid){
        tmp[i].first = nums[cur1].first;
        tmp[i++].second = nums[cur1++].second;
    }
    while(cur2<=right){
        tmp[i].first = nums[cur2].first;
        tmp[i++].second = nums[cur2++].second;
    }

    //还原
    for(int i=left;i<=right;i++){
        nums[i].first = tmp[i - left].first;
        nums[i].second = tmp[i - left].second;
    }
}
vector<int> countSmaller(vector<int>& nums){
    //注意这里不能用哈希表建立元素和下标的映射关系，因为可能存在相同的元素
    //使用哈希表会导致相同的元素统计个数相加
    //重新建立一个数组，存放原数组中的元素以及对应的下标
    vector<pair<int, int>> newnums(nums.size());
    for(int i=0;i<nums.size();i++){
        newnums[i].first = nums[i];
        newnums[i].second = i;
    }
    //通过下标找到统计数组中对应元素的位置
    vector<int> counts(nums.size());

    mergesort2(0, newnums.size()-1, newnums, counts);

    return counts;
}

int mergesort3(int left,int right,vector<int>& nums){
    //区间不存在，直接结束返回0
    if(left>=right){
        return 0;
    }

    //1.分区间
    int mid = (left + right) / 2;

    //2.递归左右子区间
    int Lret=mergesort3(left,mid,nums);
    int Rret = mergesort3(mid + 1, right, nums);

    //3.排序，统计符合的个数
    int ret = 0;
    int cur1 = left, cur2 = mid + 1;
    int i = 0;
    vector<int> tmp(right - left+1);

    while(cur1<=mid&&cur2<=right){
        if(nums[cur1]/2.0>nums[cur2]){
            ret += right - cur2 + 1;
        }
        if(nums[cur1]/2.0<=nums[cur2]&&nums[cur1]>nums[cur2]){
            for (int j = cur2+1; j <= right;j++){
                if (nums[cur1]/2.0 > nums[j]){
                    ret++;
                }
            }
        }
        tmp[i++] = nums[cur1] > nums[cur2] ? nums[cur1++] : nums[cur2++];
    }
    while(cur1<=mid){
        tmp[i++] = nums[cur1++];
    }
    while(cur2<=right){
        tmp[i++] = nums[cur2++];
    }

    //4.还原
    for(int i=left;i<=right;i++){
        nums[i] = tmp[i - left];
    }

    return ret + Lret + Rret;
}

//293.翻转对
int reversePairs1(vector<int>& nums){
    return mergesort3(0, nums.size() - 1, nums);
}

int main(){
    vector<int> nums = {2147483647,2147483647,-2147483647,-2147483647,-2147483647,2147483647};
    int ret = reversePairs1(nums);
    cout << ret;

    return 0;
}